package com.tgy.cmp;

import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-10-15 16:38
 */
public class QuickSort01<E> extends Sort<E> {

    @Override
    protected void sort() {

        sort(0,elements.length - 1);
    }


    private void sort(int begin, int end) {

        E base = elements[begin];

        int left = begin + 1,right = end;

        while (left < right) {

            while (left < right && compare(base,elements[right]) < 0) {

                right--;
            }

            while (left < right && compare(base,elements[left]) > 0) {

                left++;
            }

            if (left < right) {

                swap(left,right);
                left++;
                right--;
            }
        }

        if (compare(base,elements[left]) < 0) {

            left--;
        }

        elements[begin] = elements[left];
        elements[left] = base;


        if (begin + 1 < left) {

            sort(begin,left - 1);
        }

        if (left + 1 < end) {

            sort(left + 1,end);
        }
    }

}
